package com.cn.codebrush.数组.贪心算法;

/**
 * @Author Boolean
 * @Date 2022/5/10 23:22
 * @Version 1.0
 */
public class No45跳跃游戏II {
    public static void main(String[] args) {
        int[] nums = {2,3,1,1,4};
        System.out.println(jump(nums));
    }

    /**
     * 贪心算法
     * @param nums
     * @return
     */
    public static int jump(int[] nums) {
        int n = nums.length;
        if(n == 1){
            return 0;
        }
        int k = 0; //能走到的最大距离
        int step = 0; //步数
        int end = 0;  //上一次走到的最远的距离
        for(int i=0;i<n;i++){
            k = Math.max(k,i+nums[i]);
            if(k>=n-1){
                return step+1;
            }
            if(end == i){
                step++;
                end = k;
            }
        }
        return step;
    }
}
